# -*-coding = utf-8 -*-
# @Time : 2022/9/17 14:23
# @Author : Oliver
# @File : just-copy.py
# @Software :PyCharm
import math


def H(array, left, right):
    result = 1
    if left + 1 == right:
        return result
    if left < right:
        middle = math.floor((left + right) / 2)
        result += H(array, left, middle)
        result += H(array, middle, right)
        result += F(array, left, middle, right)
    return result


def F(array, left, middle, right):
    i = left
    j = middle
    k = 0
    result = 0
    B = []
    while i < middle and j < right:
        if array[i] < array[j]:
            B.append(array[i])
            k += 1
            i += 1
        else:
            B.append(array[j])
            k += 1
            j += 1
            result += middle - i
    while i < middle:
        B.append(array[i])
        k += 1
        i += 1
    while j < right:
        B.append(array[j])
        k += 1
        j += 1

    for i in range(k):
        array[left + i] = B[i]

    return result


# right = input()
# right = int(right)
# array = input()
# array = list(array)
array = [8, 2, 5, 4, 10, 2, 9, 4, 3, 10]
right = 10
print(H(array, 0, right))
